#include "nfa.h"
#include "dfa.h"
#include <stack>
#include <iostream>
using namespace std;

// 添加从状态n1到状态n2的转换边，转换符为ch
void addPath(NFANode* n1, NFANode* n2, char ch)
{
    // 检查n1是否已经存在以ch为转换符的转换边
    map<char, vector<NFANode*>>::iterator it = n1->nextNode.find(ch);
    if(it == n1->nextNode.end())
    {
        // 如果不存在，创建新的转换边
        vector<NFANode*> v;
        v.push_back(n2);
        n1->nextNode[ch] = v;
    }
    else
    {
        // 如果已经存在，添加到已有的转换边中
        it->second.push_back(n2);
    }
}

// 重置NFA中各个状态节点的ID
static void resetID(NFA* nfa)
{
    int i = 0;
    list<NFANode*>::iterator it = nfa->nodeList.begin();
    while (it != nfa->nodeList.end())
    {
        (*it)->id = i;
        it++;
        i++;
    }
}

// 创建只有一个字符ch的NFA
NFA* oneNFA(char ch)
{
    NFANode* n1 = new NFANode(START, 0);
    NFANode* n2 = new NFANode(END, 1);
    addPath(n1, n2, ch);
    struct NFA* nfa = new NFA(n1, n2);
    nfa->nodeList.push_back(n1);
    nfa->nodeList.push_back(n2);
    if (ch != 0)
        nfa->inputChar.insert(ch);
    return nfa;
}

// 连接两个NFA
NFA* catNFA(NFA* nfa1, NFA* nfa2)
{
    NFANode* n1 = nfa1->start;
    NFANode* n2 = nfa2->end;
    nfa1->start->nodeType = PATH;
    nfa1->end->nodeType = PATH;
    nfa1->end->nextNode = nfa2->start->nextNode;
    nfa2->end->nodeType = END;
    nfa1->nodeList.pop_front();
    nfa2->nodeList.pop_front();
    nfa2->nodeList.pop_back();
    struct NFA* nfa = new NFA(n1, n2);
    nfa->nodeList.merge(nfa1->nodeList);
    nfa->nodeList.merge(nfa2->nodeList);
    nfa->nodeList.push_front(n1);
    nfa->nodeList.push_back(n2);
    nfa->inputChar.insert(nfa1->inputChar.begin(), nfa1->inputChar.end());
    nfa->inputChar.insert(nfa2->inputChar.begin(), nfa2->inputChar.end());
    return nfa;
}

// 并联两个NFA
NFA* joinNFA(NFA* nfa1, NFA* nfa2)
{
    NFANode* n1 = new NFANode(START, 0);
    NFANode* n2 = new NFANode(END, 1);
    nfa1->start->nodeType = PATH;
    nfa1->end->nodeType = PATH;
    nfa2->start->nodeType = PATH;
    nfa2->end->nodeType = PATH;
    addPath(n1, nfa1->start, 0);
    addPath(n1, nfa2->start, 0);
    addPath(nfa1->end, n2, 0);
    addPath(nfa2->end, n2, 0);
    struct NFA* nfa = new NFA(n1, n2);
    nfa->nodeList.merge(nfa1->nodeList);
    nfa->nodeList.merge(nfa2->nodeList);
    nfa->nodeList.push_front(n1);
    nfa->nodeList.push_back(n2);
    nfa->inputChar.insert(nfa1->inputChar.begin(), nfa1->inputChar.end());
    nfa->inputChar.insert(nfa2->inputChar.begin(), nfa2->inputChar.end());
    return nfa;
}

// 重复NFA
NFA* repeatNFA(NFA* nfa)
{
    NFANode* n1 = new NFANode(START, 0);
    NFANode* n2 = new NFANode(END, 1);
    nfa->start->nodeType = PATH;
    nfa->end->nodeType = PATH;
    addPath(n1, nfa->start, 0);
    addPath(nfa->end, nfa->start, 0);
    addPath(nfa->end, n2, 0);
    addPath(n1, n2, 0);
    struct NFA* newNFA = new NFA(n1, n2);
    newNFA->nodeList.merge(nfa->nodeList);
    newNFA->nodeList.push_front(n1);
    newNFA->nodeList.push_back(n2);
    newNFA->inputChar.insert(nfa->inputChar.begin(), nfa->inputChar.end());
    return newNFA;
}

// 打印NFA
void printNFA(NFA* nfa)
{
    resetID(nfa);
    cout << "正则表达式转换为NFA结果为：" << endl;
    cout << "start: " << nfa->nodeList.front()->id << endl;
    cout << "end : " << nfa->nodeList.back()->id << endl << endl;
    list<NFANode*>::iterator lit = nfa->nodeList.begin();
    while (lit != nfa->nodeList.end())
    {
        if ((*lit)->nodeType == END) {
            lit++;
            continue;
        }
        map<char, vector<NFANode*>>::iterator mapit;
        vector<NFANode*>::iterator vit;
        for (mapit = (*lit)->nextNode.begin(); mapit != (*lit)->nextNode.end(); mapit++)
        {
            for (vit = mapit->second.begin(); vit != mapit->second.end(); vit++)
            {
                if (mapit->first != 0)
                    cout << "(" << (*lit)->id << ")" << " -- " << mapit->first << " --> " << "(" << (*vit)->id << ")" << endl;
                else
                    cout << "(" << (*lit)->id << ")" << " -- ε --> " << "(" << (*vit)->id << ")" << endl;
            }
        }
        lit++;
    }
    cout << endl;
}

// 添加从状态n1经过字符ch到状态n2的转换边
void addPath(DFA* dfa, DFANode* n1, DFANode* n2, char ch)
{
    dfa->dtrain[n1][ch] = n2;
}

// 计算状态集合s的ε闭包
static set<NFANode*> epsClosure(set<NFANode*> v)
{
    stack<NFANode*> st;
    for (auto it = v.begin(); it != v.end(); it++)
    {
        st.push(*it);
    }
    set<NFANode*> ret;
    ret.insert(v.begin(), v.end());
    NFANode* node;
    while (!st.empty())
    {
        node = st.top();
        st.pop();
        auto pair = node->nextNode.find(0);
        vector<NFANode*> epsEdge;
        if (pair != node->nextNode.end())
            epsEdge = pair->second;
        for (auto espIt = epsEdge.begin(); espIt != epsEdge.end(); espIt++)
        {
            auto it = ret.find(*espIt);
            if (it == ret.end())
            {
                ret.insert(*espIt);
                st.push(*espIt);
            }
        }
    }
    return ret;
}

// 计算状态集合stat经过字符ch到达的下一个状态集合
static set<NFANode*> nextState(Dstate* stat, char ch)
{
    set<NFANode*> v;
    for (auto it = stat->nodes.begin(); it != stat->nodes.end(); it++)
    {
        if ((*it)->nextNode.find(ch) == (*it)->nextNode.end()) continue;
        v.insert((*it)->nextNode[ch].begin(), (*it)->nextNode[ch].end());
    }
    return v;
}

// 检查集合s是否已经存在于状态集合stats中
static Dstate* isExist(set<Dstate*>* stats, set<NFANode*>* s)
{
    for (auto it = stats->begin(); it != stats->end(); it++)
    {
        if ((*it)->nodes.size() != s->size())
            continue;
        set<NFANode*> temp = (*it)->nodes;
        temp.insert(s->begin(), s->end());
        if (temp.size() == (*it)->nodes.size())
            return *it;
    }
    return nullptr;
}

DFA* NFA2DFA(NFA* nfa)
{
    // 创建一个初始状态节点和一个空的 DFA 对象
    DFANode* node = new DFANode(START, 0);
    DFA* dfa = new DFA(node);
    dfa->dtrain[node].clear();

    // 将 NFA 的输入字符集合添加到 DFA 的输入字符集合中
    dfa->inputChar.insert(nfa->inputChar.begin(), nfa->inputChar.end());

    set<Dstate*> dstates;   
    stack<Dstate*> stateStack; 
    map<Dstate*, DFANode*> state2node;

    // 创建初始状态
    Dstate* init = new Dstate();
    init->nodeType = START;
    set<NFANode*> sinit;
    sinit.insert(nfa->start);
    init->nodes = epsClosure(sinit);

    // 将初始状态入栈并加入状态集合和状态到节点的映射
    stateStack.push(init);
    dstates.insert(init);
    state2node[init] = node;

    while (!stateStack.empty())
    {
        // 取出栈顶状态并处理
        Dstate* stat, *currStat = new Dstate;
        stat = stateStack.top();
        stateStack.pop();

        // 遍历 DFA 的输入字符集合
        for(auto setIt = dfa->inputChar.begin(); setIt != dfa->inputChar.end(); setIt++)
        {
            // 获取当前状态的下一个状态集合
            currStat->nodes = nextState(stat,  *setIt);
            set<NFANode*> u;
            u = epsClosure(currStat->nodes);

            // 如果下一个状态集合为空，继续下一次循环
            if(u.empty())
            {
                continue;
            }

            // 判断下一个状态集合是否已经存在，如果不存在则创建新状态
            Dstate* nextStat = isExist(&dstates, &u);
            if(nextStat == nullptr)
            {
                Dstate* newStat = new Dstate();
                if(u.find(nfa->end) != u.end())
                {
                    newStat->nodeType = END;
                }
                else
                {
                    newStat->nodeType = PATH;
                }

                // 创建新节点并进行相关设置
                DFANode* newNode = new DFANode(newStat->nodeType, 1);
                if(newNode->nodeType == END)
                    dfa->end.push_back(newNode);
                newStat->nodes.insert(u.begin(), u.end());

                // 添加新状态到相关的数据结构中
                dstates.insert(newStat);
                stateStack.push(newStat);
                state2node[newStat] = newNode;
                dfa->dtrain[newNode].clear();
                addPath(dfa, state2node[stat], newNode, *setIt);
            }
            else
            {
                // 将转换路径添加到 DFA 中
                addPath(dfa, state2node[stat], state2node[nextStat], *setIt);
            }
        }
    }
    return dfa;
}

// 判断两个 DFA 节点是否等价
static bool isEquiv(DFA* dfa, map<DFANode*, set<DFANode*>>& s, DFANode* n1, DFANode* n2)
{
    map<char, DFANode*>& m1 = dfa->dtrain[n1];
    map<char, DFANode*>& m2 = dfa->dtrain[n2];

    // 如果两个节点的转换路径数量不一致，则认为不等价
    if(m1.size() != m2.size())
        return false;

    // 判断两个节点的每条转换路径对应的下一个节点都在等价集合中
    for(auto it = m1.begin(); it != m1.end(); it++)
    {
        if(m2.find(it->first) == m2.end() || s[m1[it->first]] != s[m2[it->first]])
            return false;
    }
    return true;
}

// 对 DFA 的状态集合进行等价划分
static vector<set<DFANode*>> splitSet(DFA* dfa, vector<set<DFANode*>> status)
{
    map<DFANode*, set<DFANode*>> node2set;

    // 构建节点到状态集合的映射
    for(auto stat : status)
    {
        for(auto n : stat)
        {
            node2set[n] = stat;
        }
    }

    // 创建新的状态集合
    vector<set<DFANode*>> newStatus;
    for(auto st : status)
    {
        if(st.size() == 1)
        {
            newStatus.push_back(st);
            continue;
        }

        bool issplit = false;
        map<DFANode*, int> newmap;
        int i = 0;

        // 对每个状态集合进行等价划分
        for(auto it1 = st.begin(); it1 != st.end(); it1++)
        {
            if(newmap.find(*it1) == newmap.end())
            {
                newmap[*it1] = i;
                i++;
            }
            else
            {
                continue;
            }

            for(auto it2 = it1; it2 != st.end(); it2++)
            {
                if(it2 == it1)
                    continue;
                if(it2 == st.end())
                    break;
                if(isEquiv(dfa, node2set, *it1, *it2))
                {
                    newmap[*it2] = newmap[*it1];
                }
            }
        }

        map<int, set<DFANode*>> res;
        for(auto p : newmap)
        {
            res[p.second].insert(p.first);
        }

        for(auto p : res)
        {
            newStatus.push_back(p.second);
        }
    }

    return newStatus;
}

// 对 DFA 进行最小化
DFA* minDFA(DFA* dfa)
{
    DFA* minDfa = new DFA(nullptr);
    vector<set<DFANode*>> status;
    set<DFANode*> notEnd;
    set<DFANode*> endNode;

    // 划分初始的状态集合，包含非终态和终态
    for(auto p : dfa->dtrain)
    {
        if(p.first->nodeType == END)
        {
            endNode.insert(p.first);
        }
        else
        {
            notEnd.insert(p.first);
        }
    }

    status.push_back(notEnd);
    status.push_back(endNode);
    int setNum = 0;

    // 进行等价划分，直到状态集合不再发生变化
    while(status.size() != setNum)
    {
        setNum = status.size();
        status = splitSet(dfa, status);
    }

    int i = 0;
    map<DFANode*, DFANode*> node2id;

    // 创建最小化的 DFA
    for(auto it = status.begin(); it != status.end(); it++)
    {
        DFANode* node = new DFANode(PATH, i);
        NODETYPE ntype = PATH;
        for(auto setIt = (*it).begin(); setIt != (*it).end(); setIt++)
        {
            node2id[*setIt] = node;
            if((*setIt)->nodeType == START)
            {
                ntype = START;
            }
            else if((*setIt)->nodeType == END)
            {
                ntype = END;
            }
            
        }
        node->nodeType = ntype;
        if(ntype == START)
            minDfa->start = node;
        else if(ntype == END)
            minDfa->end.push_back(node);
        i++;
    }

    // 将转换路径添加到最小化的 DFA 中
    for(auto it = node2id.begin(); it != node2id.end(); it++)
    {
        DFANode* node = it->second;
        for(auto charIt = dfa->inputChar.begin(); charIt != dfa->inputChar.end(); charIt++)
        {
            auto nextIt = dfa->dtrain[it->first].find(*charIt);
            if(nextIt != dfa->dtrain[it->first].end())
                addPath(minDfa, node, node2id[nextIt->second], *charIt);
        }
    }

    // 移除没有出边的节点
    vector<DFANode*> removeNode;
    for(auto p : minDfa->dtrain)
    {
        if(p.first->nodeType != PATH)
            continue;

        bool flag =  true;
        for(auto nextIt = minDfa->dtrain[p.first].begin(); nextIt != minDfa->dtrain[p.first].end(); nextIt++)
        {
            if(nextIt->second->id != p.first->id)
            {
                flag = false;
                break;
            }
        }

        if(flag)
            removeNode.push_back(p.first);
    }

    for(auto it = removeNode.begin(); it != removeNode.end(); it++)
    {
        minDfa->dtrain.erase(*it);
    }

    cout<<"最小化";
    return minDfa;
}



static void resetID(DFA* dfa)
{
    int i = 0;
    for(auto p : dfa->dtrain)
    {
        p.first->id = i++;
    }
}


void printDFA(DFA* dfa)
{
    resetID(dfa);
    cout << "NFA转DFA如下：" << endl;
    cout << "start: " << dfa->start->id << endl;
    cout << "end: " ;
    for(auto n : dfa->end)
        cout << n->id << " ";
    cout << endl << endl;
    for(auto p : dfa->dtrain)
    {
        for(auto mapit : p.second)
        {
            cout <<"(" << p.first->id << ")" << " -- " << mapit.first << " --> " <<"(" << mapit.second->id << ")" << endl;
        }
    }
    cout << endl;
}
